package _07_串;

/**
 * https://leetcode-cn.com/problems/regular-expression-matching/
 * @Author: haogege
 * @Date: 2021/9/20
 */
public class _10_正则表达式匹配 {

    public static void main(String[] args) {


        String s1 = "aa";
        String p1 = "a*";

        System.out.println(isMatch(s1, p1));
    }


    public static boolean isMatch(String s, String p) {

        char[] s1 = s.toCharArray();
        char[] p1 = p.toCharArray();

        int len1 = s1.length;
        int len2 = p1.length;
        // dp数组表示s的前i个元素和p的前j个元素的匹配情况
        boolean[][] dp = new boolean[len1 + 1][len2 + 1];
        // 初始化数据，空字符匹配为真
        dp[0][0] = true;
        for (int i = 0; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) { // 匹配字符从1开始，因为存在.的情况
                // 判断当前字符是否为*号
                if (p1[j - 1] == '*') { // 当匹配到*一定是第二个字符
                    if (matches(s1, p1, i, j - 1)) {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }
                } else {
                    dp[i][j] = matches(s1, p1, i, j) && dp[i - 1][j - 1];
                }
            }
        }

        return dp[len1][len2];
    }


    public static boolean matches(char[] s, char[] p, int i, int j) {
        if(i == 0) {
            return false;
        }
        if(p[j - 1] == '.') {
            return true;
        }
        return s[i - 1] == p[j - 1];
    }

}
